/*
Algorithms:  brief Definition of algorithms classes from thrust to fui.
    Copyright (C) 2012  Jorge E. A. Atala
                        FuDePAN
    This file is part of the Fui Proyect.

    Fui is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    Fui is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with Fui.  If not, see <http://www.gnu.org/licenses/>.
*/

#ifndef ALGORITHMS_H
#   define ALGORITHMS_H
#   include <thrust/reduce.h>
#   include <thrust/transform.h>
#   include <thrust/partition.h>
#   include <thrust/unique.h>

namespace fui
{
using thrust::reduce;
using thrust::transform;
using thrust::find;
using thrust::find_if;
using thrust::mismatch;
using thrust::partition;
using thrust::stable_partition;
using thrust::remove;
using thrust::remove_copy;
using thrust::remove_if;
using thrust::unique;
using thrust::unique_copy;
using thrust::swap_ranges;

template <class Iterator>
__host__ __device__
void plusOne(Iterator begin, const Iterator end)
{
    for (; begin != end; ++begin)
        ++(*begin);
}

template<class InputIterator, class OutputIterator , class CombinatorialFunction>
__global__
void combinationsWithoutRepositionKernel(InputIterator begin,
        OutputIterator output,
        CombinatorialFunction op,
        const unsigned int combinations,
        const size_t totalCombinations)
{
    const size_t outputPosition = blockIdx.x * blockDim.x + threadIdx.x;
    size_t tid = outputPosition + 1;
    if (tid <= totalCombinations)
    {
        device_vector<size_t>::type positions(combinations, 0);
        device_vector<size_t>::type::iterator begin = positions.begin();
        const device_vector<size_t>::type::iterator end = positions.end();
        size_t value = 0;
        size_t maxPosition = totalCombinations - combinations;
        size_t sumElement = maxPosition + 1;
        size_t dif = 1;
        for (unsigned int it = 2; it <= sumElement; ++it)
            dif += it;
        for (unsigned int it = 1; it < combinations; ++it)
            positions[it] = ++value;
        for (unsigned int it = 0; it < combinations; ++it)
        {
            while ((tid - dif) > 0)
            {
                plusOne(begin, end);
                dif = (sumElement == 1) ? 1 : (dif - sumElement--);
                tid -= dif;
            }
            positions[it] = ((maxPosition < positions[it]) ? maxPosition : positions[it]);
            dif = (sumElement == 1) ? 1 : (dif - sumElement--);
        }
        *(output + outputPosition) = op(make_permutation_iterator(begin, positions.begin()),
                                        make_permutation_iterator(begin, positions.end()));
    }
}

template<class InputIterator, class OutputIterator , class CombinatorialFunction>
__global__
void combinationsWithRepositionKernel(InputIterator begin,
                                      OutputIterator output,
                                      CombinatorialFunction op,
                                      const unsigned int combinations,
                                      const size_t totalCombinations)
{


}

class Combinator
{
    const size_t blockSize;

protected:

    size_t summatoria(size_t n)
    {
        size_t result = n;
        while (n != 0)
            result += --n;
        return result;
    }

public:
    Combinator(size_t _blockSize)
        :   blockSize(_blockSize)
    {}

    Combinator()
        :   blockSize(128)
    {}

    template<class InputIterator, class OutputIterator , class CombinatorialFunction>
    void combinationsWithoutReposition(InputIterator& begin,
                                       const InputIterator& end,
                                       OutputIterator& output,
                                       CombinatorialFunction& op,
                                       const unsigned int combinations)
    {
        size_t totalCombinations = end - begin;
        //if(combinations == 2)
        //    totalCombinations = summatoria(totalCombinations - 1);
        if (combinations > 2)
        {
            for (size_t  it = totalCombinations - (combinations - 1) ; it > 0; --it)
                totalCombinations += summatoria(it);
        }
        size_t grid = totalCombinations / blockSize + ((totalCombinations % blockSize) ? 1 : 0);
        combinationsWithoutReposition <<< grid, blockSize >>>(begin, output, op, combinations, totalCombinations);
    }

    template<class InputIterator, class OutputIterator , class CombinatorialFunction>
    void combinationsWithReposition(InputIterator& begin,
                                    const InputIterator& end,
                                    OutputIterator& output,
                                    CombinatorialFunction& op,
                                    const unsigned int combinations)
    {


    }
};



}
#endif











